/*
Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

1
/ \
2   3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.
*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}










class Solution {
public:
	void dfs(int &sum,vector<int> &tempInt, TreeNode* root)
	{
		if (root->left==NULL&&root->right==NULL)
		{
			tempInt.push_back(root->val);
			//int size = tempInt.size();
			for (int i = tempInt.size() - 1,j= 0; i >=0 ; i--,j++)
			{
				sum += (tempInt[j] * pow(10, i));
			}
			tempInt.pop_back();
			return;
		}

		tempInt.push_back(root->val);
		if (root->left != NULL)dfs(sum,tempInt,root->left);
		if (root->right != NULL)dfs(sum, tempInt, root->right);
		
		tempInt.pop_back();
		return;
		
		

		


	}
	int sumNumbers(TreeNode* root) {
		if (root ==NULL)
		{
			return 0;
		}
		
		int sum = 0;
		vector<int> tempInt;
		dfs(sum,tempInt,root);
		return sum;

	}
};


int main(int argc, char* argv[])
{



	string start = "hit";
	string end = "cog";


	//std::unordered_set<std::string> myset =
	//{ "hot", "dot", "dog", "lot", "log" };

	//std::cout << "myset contains:";
	// for (auto it = myset.begin(); it != myset.end(); ++it)
	//std::cout << " " << *it;
	//;; std::cout << std::endl;

	TreeNode *root = new TreeNode(1);
	TreeNode *left = new TreeNode(2);
	TreeNode *right = new TreeNode(3);

	root->left = left;
	root->right = right;







	Solution s;
	int length = s.sumNumbers(root);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}